package 数据结构系列;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

public class 下一个更大元素I_496 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new 下一个更大元素I_496().nextGreaterElement(
                new int[]{4, 1, 2}, new int[]{1, 3, 4, 2}))
        );


    }


    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();

        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
                 stack.pop();//注意，到这里nums2[i]就算满足条件也还没入栈
            }
            map.put(nums2[i],stack.isEmpty()?-1:stack.peek());
            stack.push(nums2[i]); // 入栈
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }


//    public int[] nextGreaterElement2(int[] nums) {
//        Deque<Integer> stack = new LinkedList<>();
//        int[] ans = new int[nums.length];
//
//        for (int i = nums.length - 1; i >= 0; i--) {
//            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
//                stack.pop();
//            }
//            ans[i]=stack.isEmpty()?-1:stack.peek();
//            stack.push(nums[i]); // 入栈
//        }
//
//        return ans;
//    }
}
